Ликбез по производной, градиент и метод градиентного спуска

---

library(plotly)
library(dplyr)
library(tibble)
library(ggplot2)
library(tidyr)

Функция и ее производная

Вспомним, что функция – это отображение одного множества в другое, но так, что каждому элементу одного множества соответствует один и только один элемент из другого множества. Записывается это так: \(f: \mathbb{R}^n \rightarrow \mathbb{R}\).

Вспомним простую функцию \(y = x^2\). Давайте нарисуем её!

square <- function(x){
  return(x^2)
}

df <- tibble(x = seq(-30, 30, by = 0.1),
             y = square(x))

ggplot(df, aes(x, y)) +
  geom_line()

В данном случае \(y\) – это функция от одной переменной \(x\). На таком графике мы можем явно увидеть зависимость функции от ее аргумента. Видим, что минимум находится в точке \(x = 0\). Чуть позже мы будем работать с функциями нескольких переменных.

Теперь вспомним что такое производная. Не будем лезть в тяжелую математику. Нам будет важно следующее определение. Производная – скорость изменения функции в данной точке.

Вспомним некоторые производные:

1. \(c' = 0, c = const\)
2. \((x^n)' = nx^{n-1}\)
3. \((e^x)' = e^x\)
4. \((\ln{x})' = \frac{1}{x}\)
5. \((\sin{x})' = \cos{x}\)
6. \((\cos{x})' = -\sin{x}\)

А также некоторые свойства:

1. \((cf(x))' = cf'(x)\) – константу можно вынести из под знака производной
2. \((f(x) + g(x))' = f'(x) + g'(x)\) – производная суммы это сумма производных
3. \([f(g(x))]' = f'(g(x))g'(x)\) – производная сложной функции

А теперь порешаем некоторые примеры, чтобы лучше с этим разобраться.

1. \(y = 100\)
2. \(y = x^2\)
3. \(y = 5x\)
4. \(y = 10x^3\)
5. \(y = 4x + cos(x)\)
6. \(y = \ln(x^2)\)
7. \(y = (10 - 5x)^2\)

Давайте возьмем функцию \(y = x^2\). Представим, что мы находимся в точке \(x_0 = 5\). Значение функции в этой точке равно 25.

x0 <- 5
ggplot(df, aes(x, y)) +
  geom_line() + 
  geom_point(x = x0, y = square(x0), color = 'blue', size = 2)

Производная этой функции: \(y' = 2x\). . Давайте найдем ее производную в этой точке.

der_square <- function(x){
  return(2*x)
}

der_square(x0)

## [1] 10

Производная в этой точке равна 10. Важное свойство производной состоит в том, что если производная положительна, то чтобы увеличить значение функции надо увеличивать значение аргумента. Аналогично, если мы хотим уменьшить значение функции, мы должны уменьшить аргумент. Если значение производной в точке отрицательно, то все ровно наоборот.

Объединяя эти два случая получаем:

\(x_1 = x_0 + sign(f'(x_0)) t\)

Второй вопрос, а на сколько нужно увлечивать или уменьшать?

Минимум функции от одного аргумента

В школе нас учили находить минимум или максимум функции. Нужно было найти первую производную, приравнять ее к нулю и дело почти в шляпе. Оставалось только решить уравнение и проверить точки на минимум и максимум или найти вторую производную и понять по ней. Мы отойдем от этого подхода и будем искать минимум немного по-другому. Позже мы поймем почему мы отошли от стандартного метода.

Метод градиентного спуска (GD)

Изучим метод градиентного спуска. Его смысл заключается в том, чтобы итеративно искать минимум функции. Давайте вернемся к функции \(y = x^2\). Изначально мы не знаем в какой точке находится минимум этой функции. Давайте выберем рандомно какое-то число. Пусть это будет \(x_0 = 10\). Если мы найдем производную функции в этой точке, то поймем в какую сторону нам нужно двигаться, чтобы увеличить значение функции. Мы пойдем в обратную сторону, так как мы хотим минимизировать нашу функцию. Поэтому изменим значение нашего аргумента \(x_0\) на величину производной. Только эта величина может принимать достаточно большие значения, поэтому давайте умножим ее на константу \(\alpha\), которую мы будем задавать сами. Эта константа называется скорость обучения.

\[x_t = x_{t-1} - \alpha \frac{df(x)}{dx} \bigg|_{x=x_{t-1}}\]

После того как мы сделали одну итерацию мы проделали шаг градиентного спуска. Будем продолжать его делать, пока функция не начнет уменьшаться на очень маленькую величину. Давайте попробуем проделать это в коде и визуализировать.

alpha <- 0.1
x0 <- 10

for(i in 1:20){
  p <- ggplot(df, aes(x, y)) +
        geom_line() + 
        geom_point(x = x0, y = square(x0), color = 'blue', size = 2)
  print(p)
  x0 <- x0 - alpha * der_square(x0)
  readline('Enter:')
}

Скорость обучения это важная штука. Давайте попробуем ее уменьшить.

alpha <- 0.01
x0 <- 10

for(i in 1:20){
  p <- ggplot(df, aes(x, y)) +
        geom_line() + 
        geom_point(x = x0, y = square(x0), color = 'blue', size = 2)
  print(p)
  x0 <- x0 - alpha * der_square(x0)
  readline('Enter:')
}

Видно, что сходимость стала заметно медленее. А теперь давайте попробуем увеличить скорость обучения.

alpha <- 1.2
x0 <- 10

for(i in 1:5){
  p <- ggplot(df, aes(x, y)) +
        geom_line() + 
        geom_point(aes(x = x0, y = square(x0)), color = 'blue', size = 2)
  print(p)
  x0 <- x0 - alpha * der_square(x0)
  readline('Enter:')
}

Случилось ужасное. Мы перескакиваем наш минимум и алгорим начинает расходится. Со скоростью обучения надо быть аккуратнее.

Давайте возьмем функцию поинтересней.

our_function <- function(x){
  y <- 10 * cos(x) + 0.5*x^2 -5*x
  return(y)
}

df <- tibble(x = seq(-10,10, by = 0.01),
             y = our_function(x))

ggplot(df, aes(x, y)) +
  geom_line()

Вот такая интересная функция. Найдем ее производную.

der_our_function <- function(x){
  y <- -10*sin(x) + x - 5
  return(y)
}

Попробуем найти минимум с помощью GD.

x0 <- -10
alpha <- 0.01
for(i in 1:100){
  p <- ggplot(df, aes(x, y)) +
    geom_line() +
    geom_point(x = x0 , y = our_function(x0), color='red')
  # print(p)
  x0 <- x0 - alpha * der_our_function(x0)
  # readline('Enter:')
}
print(p)

Мы попали в локальный минимум и никак не можем из него выбраться. Можно попробовать настроить скорость обучения и попасть в минимум. Но в реальной задаче мы не будем видеть минимум так хорошо на графике. Здесь есть несколько решений. Нужно пытаться запускать GD из нескольких рандомных точек или использовать более мощные алгоритмы градиентного спуска.

Например, Momentum GD. Momentum это метод, который помогает стохастическому градиентному спуску сохранять направление движения. Это осуществляется за счёт добавления в выражение дополнительного слагаемого: накопленного за предыдущие шаги градиента с весом \(\alpha\).

\[ \nu_t = \alpha \nu_{t-1} + \eta \frac{df(x)}{dx} \bigg|_{x=x_0}\] \[ x_t = x_{t-1} - \nu_t\]

x0 <- -10
eta <-  0.05
alpha <-  0.7
nu <- 0

for(i in 1:30){
  p <- ggplot(df, aes(x, y)) +
    geom_line() +
    geom_point(x = x0 , y = our_function(x0), color='red')
  # print(p)
  nu <-  alpha * nu + eta * der_our_function(x0)
  x0 <-  x0 - nu
  # readline('Enter:')
}
print(p)

Функция нескольких переменных

До этого мы рассматривали функции от одной переменной. В будущем нам нужно будет работать с функциями нескольких переменных. Записывать их будем следующим образом:

\[f(x_1, x_2, ..., x_n)\] или коротко

\[f(\vec x).\] Давайте посмотрим на функцию от двух переменных \(y = x_1^2 + x_2^2\).

our_function <- function(x1, x2){
  z <- x1^2 + x2^2
  return(z)
}

n <- 300
x1 = seq(-10, 10, length.out = n)
x2 = seq(-10, 10, length.out = n)
z <- matrix(data = 0, nrow = n, ncol = n)
for(i in 1:nrow(z)){
  for(j in 1:ncol(z)){
    z[i,j] <- our_function(x1[i], x2[j])
  }
}

pp <- plot_ly(z = z, x = x1, y = x2, type = "surface")
pp

Как же находить минимум для функций нескольких переменных? Вместо производной в нашей формуле будет градиент. Градиент – это вектор частных произвродных.

\[ \vec x_t = \vec x_{t-1} - \alpha \nabla f(\vec x), \] где

\[ \nabla f(\vec x) = (\frac{\partial f(x)}{\partial x_1}, ..., \frac{\partial f(x)}{\partial x_n}).\]

Например, при подсчете частной производной \(\frac{\partial f(x)}{\partial x_1}\) мы просто находим производную функции по \(x_1\), а все остальные переменные считаем константой.

Для функции \(y(\vec x) = x_1^2 + x_2^2\) частная производная по переменной \(x_1\) будет равна

\[\frac{\partial y(\vec x)}{\partial x_1} = 2x_1.\]

Потренируемся на примерах. Найдем частные производные.

• \(y = x_1 x_2\)
• \(y = x_1 x_2^2\)
• \(y = (3x_1 - 2x_2)^2\)

Веса будут меняться аналогично. Давайте возьмем точку $x_0 = (9, -8) $ и попробуем найти минимум градиентным спуском.

our_function <- function(x1, x2){
  z <- x1^2 + x2^2
  return(z)
}

der_x1 <- function(x1){
  k <- 2*x1
  return(k)
}

der_x2 <- function(x2){
  k <- 2*x2
  return(k)
}

GD <- function(x1, x2, alpha=0.05){
  x <- c(x1, x2)
  x <- x - alpha * c(der_x1(x[1]), der_x2(x[2]))
  return(x)
}

df <- tibble(x1 = double(), x2 = double(), z = double())

x1 <- 9
x2 <- -8
iter <- 30

for(i in 1:iter){
  step <- GD(x1, x2)
  x1 <- step[1]
  x2 <- step[2]
  z <- our_function(x1, x2)
  df <- add_row(df, x1 = x1, x2 = x2, z = z)
  # readline('Enter:')
}

n <- 300
x1 = seq(-10, 10, length.out = n)
x2 = seq(-10, 10, length.out = n)
z <- matrix(data = 0, nrow = n, ncol = n)
for(i in 1:nrow(z)){
  for(j in 1:ncol(z)){
    z[i,j] <- our_function(x1[i], x2[j])
  }
}

pp <- plot_ly(z = z, x = x1, y = x2, type = "surface") %>%
        add_markers(x = df$x1, y = df$x2, z = df$z, size = 30) %>%
        add_lines(x = df$x1, y = df$x2, z = df$z, size = 30)
pp

---